# 阶乘约数(好题, 质因数分解)

def count_factor(num):
    """类似于汉密顿回路, 暴力算法时间复杂度为O(n!)"""
    factors = set()

    def backtrack(path, mult, curr):
        nonlocal factors
        if curr in path:
            return
        path.add(curr)
        if not mult in factors:
            factors.add(mult)

        for i in range(1, num + 1):
            if i in path:
                continue
            backtrack(path, mult * i, i)
            path.remove(i)

    backtrack(set(), 1, 1)
    return len(factors)


def count_factor_divisor_theorem(num):
    """
    使用约数个数定理进行计算
    约数个数定理:
    设一个正整数n可以表示为下式:
        n = p1^a1 * p2^a2 .... * pk^ak
    其中, p1,p2....pk为质数, 而 a1,a2....ak为正整数, 那么n的约数的个数d(n)可由下式计算:
        d(n) = (a1 + 1) * (a2 + 1) * .... * (ak + 1)
    这是因为正整数n的任意一个约数都可以写成
        p1^b1 * p2^b2 ... * pk^bk  其中bi可以为0
    例如 n = 72 = 2^3 * 3^2
    那么任意选择2的指数0<=a1<=3, 再任意选择3的指数0<=a2<=2
    所以72的约数的个数为 (3+1) * (2+1) = 12

    P.S.:
    约数和定理:
    一个正整数n的所有约数的和可以表示为:
    s = (p1^0 + p1^1 + ... + p1^a1) * (p2^0 + p2^1 + ... + p2^a2) * ..... * (pk^0 + pk^1 + .... + pk^ak)
    """

    fact_cnt = [0] * (num + 1)  # 存储质因数的个数

    def qualify_factor(num):
        """
        构造函数分解质因数（短除法）
        """
        nonlocal fact_cnt
        fact = 2  # 初始质数因子
        while num >= fact:
            if num % fact == 0:
                fact_cnt[fact] += 1
                num /= fact
            else:
                fact += 1

    for i in range(1, num + 1):  # 对每一个数字进行质因数分解
        qualify_factor(i)

    res = 1
    for cnt in fact_cnt:
        if cnt != 0:
            res *= (cnt + 1)
    return res


if __name__ == '__main__':
    print(count_factor_divisor_theorem(100))
